package two.chapter_5.c5_3;

import edu.princeton.cs.algs4.StdOut;

/**
 * 暴力子字符串查找
 */
public class ViolenceSearch {

    public static int search(String pattern,String txt){
        int M=pattern.length();
        int N=txt.length();
        int i,j;
        for (i=0,j=0;i<N && j<M;i++){
            if (txt.charAt(i) == pattern.charAt(j)){
                j++;
            }else {
                i-=j;
                j=0;
            }
        }
        if (j==M) return i-M;
        return N;
    }

    public static int searchp(String pattern,String txt){
        int M=pattern.length();
        int N=txt.length();
        int i,j;
        for (i=0,j=0;i<N && j<M;i++){
           if (txt.charAt(i)==pattern.charAt(j)){
               j++;
           }else {
               i-=j;//不匹配时显示回退i指针
               j=0;
           }

        }
        if (j==M) return i-M;
        return N;
    }
    /**
     * @param pattern
     * @param txt
     * @return
     */
    public static int search2(String pattern,String txt){
        int M=pattern.length();
        int N=txt.length();
        for (int i=0;i<=N-M;i++){
            int j;
            for (j=0;j<M;j++){
                if (txt.charAt(i+j)!=pattern.charAt(j)){
                    break;
                }
            }
            if (j==M)
                return i;//找到匹配
        }
        return N;

    }
    public static int search1(String pattern,String txt){
        int index=-1;
        int i=0;
        int j=0;
        while (i<txt.length()&& j<pattern.length()) {
            char c = txt.charAt(i);
            char pc = pattern.charAt(j);
            if (c == pc) {
                i++;
                j++;
            }else {
                i++;
                j=0;
            }
        }
        if (j==pattern.length()){
            index=i-pattern.length();
        }
        return index;

    }


    public static void main(String[]args){
        int index=ViolenceSearch.search("wind","agsfswindfs");
        StdOut.println("index:"+index);

    }
}
